1. Field of the Invention
This invention relates generally to data processing systems and more particularly to information protection hardware and techniques.
2. Description of the Prior Art
Computer systems have grown from the simple batched systems, wherein the valuable resource of random access memory was allocated to a single program, to the present day multiprogramming, multiprocessing systems wherein information is shared among a community of users. In this type of shared environment protection of shared information is required not only to maintain user security and privacy and restrict access of information to those users entitled to it, but to guarantee system integrity and reliability by limiting the propagation of errors through intentional or unintentional altering of shared information. Hence the relatively simple problem of protecting the supervisor from the user in a batch system has been magnified several times because of the requirement that information be flexibly shared not only between system and user but between user and user.
Several schemes have been utilized in the past in order to protect information. Some of them are detailed by Robert M. Graham in a paper entitled "Protection in an Information Processing Utility", published in CACM (May 1968).
One such method restricts access of inactive information on various storage mediums by providing a mode switch for executing instructions in one of two modes--master or slave. Under this scheme there are privileged instructions and non-privileged instructions. When the mode switch is set in master-mode all instructions may be executed whereas if the mode switch is set in slave mode only the non-privileged instructions may be executed. To protect active information in working store, the memory is further partitioned so that all of the memory is available when executing in master mode, but only a portion of the memory is available when executing in slave mode. A memory bounds register in conjunction with the mode switch is utilized to set the bounds of accessability.
This type of memory protection is inadequate for present day multiprogramming systems because there is no provision for gradations of privilege or gradations accessability, and severely limits the control over access to information. There should be provisions for different access rights to the different types of information. A partial answer to this problem is found in the concept of a memory having a segment as the unit of information to which access is controlled. Varying degrees of access to each segment is possible by providing for different types of privileges attached to each segment such as master/slave, write/no-write and execute/no-execute. However, this method of protecting the privacy and integrity of information does not take into account the user of the information. Under this type of protection, privilege is not accorded the user but the information being protected. Hence a user if he has access at all to a segment has access similar to all other users who have access to the segment. David C. Evans and Jean Yves LeClerc in a paper entitled "Address Mapping and the Control of Access in an Interactive Computer," SJCC 1967, recognized the problem and attempted a solution. Evans and LeClerc said in that article p. 23, "The user of a computing system should be able to interact arbitrarily with the system, his own computing processes, and other users in a controlled manner. He should have access to a large information storage and retrieval system called the file system. The file system should allow access by all users to information in a way which permits selectively controlled privacy and security of information. A user should be able to partition his computation into semi-independent tasks having controlled communication and interaction among tasks. Such capability should reduce the human effort required to construct, debug, and modify programs and should make possible increased reliability of programs. The system should not arbitrarily limit the use of input/output equipment or limit input/output programming by the user." Evans and LeClerc proposed conditioning access rights on the procedure-in-execution. The segment, under their proposal, is still the unit of information to which access is controlled; however, a segment's access control attributes are recorded substantially in a user-name versus procedure tables whose entries are the access modes. Such a solution, however, has serious drawbacks. For one, the construction and updating of each segment's table of access control attributes presents a formidable task. For another, too many uses of the segment and event occurrences must be foreseen. To overcome this problem access control by procedure-set was suggested. Under this suggestion, related procedures are grouped into "sets of procedures" and access rights to segments is based on the identity of the set to which the procedure seeking access belongs. This method alleviated the problem of constructing and updating each segment's voluminuous tables of access control attributes, but introduced the problem of determining to which set a given procedure belonged, particularly when a procedure was or could be a number of many sets. This ambiguity in defining sets, and the possible transitions between sets makes the implementation of access control based on "sets of procedures" extremely difficult.
To overcome the difficulties encountered with the "set" technique a ring concept was developed. The ring concept groups the sets of procedures into rings that can unambiguously be ordered by increasing power or level of privilege. By assigning a collection of sets to a collection of concentric rings, and assigning numbers to each ring with the smallest ring having the smallest number and each succeeding larger ring having a progressively greater number, different levels of privilege can then be unambiguously assigned to the user of a segment. Under this concept the innermost ring having the smallest number assigned to it has the greatest privilege. Hence it can be postulated that users in the lowest ring number can access information having higher ring numbers, but users in a higher ring number cannot access information having lower ring numbers or can access information in a lower ring number only in a specified manner. This palpable change of power or level of privilege with a change in rings is a concept which overcomes the objections associated to a change of sets.
Multics (Multiplexed Information and Computing Service) is an operating system developed primarily by Massachusetts Institute of Technology, in cooperation with General Electric Co. and others which first utilized the ring theory of protection in software on a converted Honeywell 635 computer and later on a Honeywell 645 computer. The Multics philosophy utilizes 64 rings of protection numbered as rings 0-63 and is set forth generally in a paper entitled "Access Control to the Multics Virtual Memory" published by Honeywell Information Systems Inc. in the Multics Technical Papers, Order No. AG95, Rev. 0. A more detailed description of Multics ring protection is to be found on chapter 4 of a book entitled "The Multics System; An Examination of its Structure," by Elliott I. Organick, published by MIT Press, and also in the Multics System Programmers Manual 1969, MIT Project MAC. Briefly, the Multics system does not utilize a "pure ring protection strategy" but rather employs the "ring bracket protection strategy" wherein a user's access rights with respect to a given segment are encoded in an access-mode and a triple of ring number (r1, r2, r3) called the user's "ring brackets" for a given segment. A quotation from pages 137-139 from the Multics Technical Paper entitled, "Access Control to the Multics Virtual Memory" sets out the rules and conditions for using and changing rings. "The Rules. The ring brackets, (r1, r2, r3), which must satisfy the relations r1&lt;r2&lt;r3, are interpreted as follows. (Note that all ring intervals are inclusive).
a. If the user's access-mode contains WRITE the user may, in rings (0, r1), write in the segment. PA1 b. If the user's access-mode contains READ the user may, in rings (0, r2), read the segment. PA1 c. If the user's access-mode contains EXECUTE the user may: PA1 d. All ring switching must be done under the supervision of the access control mechanism. PA1 e. The concept of `return from a call` must be extended to imply a return to the caller's ring. "Under these rules we see that a utility routine may be given ring-brackets (0,63,63) and so be callable in all rings, but never occasion a change of rings upon being called. On the other hand, a critical system procedure might have ring brackets (0,0,0) and so be callable and executable only in ring 0. PA1 accessible in master mode only, PA1 master mode procedure; PA1 faulting, PA1 taking an interrupt." PA1 a. If the SDW implies a particular "directed fault", then that fault occurs. PA1 b. Otherwise, if the SDW does not permit the attempted access, the appropriate access violation fault occurs.
1. in rings (r1, r2) call the segment without changing rings; PA2 2. in rings (0, r1-1), call the segment, switching to ring r1; PA2 3. in rings (r2+1, r3), call the segment switching to ring r2.
Every attempt by the process to switch to a lower numbered ring in this way must pass a legitimacy test imposed by the access control mechanism and by the procedure being entered.
"We also see that a user who has read and write permission for a data segment may be given ring brackets (a,b,b) with a b so that the domain in which he has write permission, ring (0,a) is a relatively privileged subset of the domain in which he has read permission, ring (0,b). These comments show how the ring bracket strategy corrects the defects which we noticed in the preliminary strategy.
"Ring Changing Calls. Let us now discuss inward and outward calls. The `rules` provide that every procedure segment for which 0 r1 may be entered via an outward call (from ring 0, for instance) and that those procedure segments for which r2&lt;r3 are `gate` segments and may, therefore, be entered via inward calls (from ring r3, for instance).
"An inward call is made when a procedure in an outer ring wants to increase the power of its process temporarily in order to do a job requiring such increased power. For example, a user procedure may call a system procedure in ring 0. The notion of "inward call" brings to mind "the tail wagging the dog", since lesser power directs the user of greater power. The only segments which can be entered via inward calls are, therefore the `gate` segments. The duty of a gate segment, is to perform a test of the legitimacy of the inward call, that is, to see that the caller has not, by accident or design, asked the gate segment to behave irresponsibly. Whether or not a segment is a `gate` for a particular user depends on that user's ring brackets and access-mode respecting that segment.
"An outward call is made when a procedure executing in an inner ring wants a job done which can (and perhaps must) be accomplished with the comparatively feebler power of an outer ring. For example, a process in Multics initializes itself (a system function) in ring 0 but calls out to a user ring when ready to do the user's work. In this case, the process must call out since a Multics convention forbids user work to be done in ring 0. For another example, a programmer with a collection of more or less debugged procedures may use several rings, keeping the more debugged procedures and their data in the inner rings so that damage from the other procedures will be isolated in the outer rings. If these procedures call each other freely, outward calls will presumably occur."
"The above described "ring protection concept" was first implemented with software techniques utilizing 64 separate rings. Subsequently an attempt was made to define a suitable hardware base for ring protection. The Honeywell 645 computer represents a first such attempt. The Honeywell 645 system differs from the "ringed hardware" concepts described supra in several respects which when taken together, and up to the fact that the Honeywell 645 is a 2-ring rather than a 64-ring machine, and has in lieu of a "ring register", a master mode and a slave mode, which imparts greater power to the processor when in master mode than when in a slave mode. "The access control field of the 645's SDW (segment descriptor word) contains no information about rings; in particular it does not contain ring brackets. It does, however, contain either:
(a) access-mode information possibly including either of the two descriptors;
(b) the specification of one of eight special `directed` faults (traps) which is to occur whenever the segment descriptor words (SDW) is accessed.
"The procedure is only `in master mode` when executing a procedure whose SDW indicates a `master mode procedure.` The processor may enter master mode while executing a slave mode procedure by:
"The 645 processor's access control machinery interprets the SDW during the addressing cycle and causes the appropriate action to occur depending on the SDW and (usually) on the attempted access, as follows:
Otherwise, the SDW permits the attempted access and the access is performed.
"When a fault occurs, the 645 enters master mode and transfers control to the appropriate master mode fault handling procedure." (Access Control to the Multics Virtual Memory, supra pps. 157-158).
Another paper by Michael D. Schroeder and Jerome H. Saltzer entitled "A Hardware Architecture for Implementing Protection Rings" published in Communications of the ACM, March 1972 Vol. 15, No. 3, sets forth background and theory of ring protection and describes a hardware implementation of "ring protection."
Because the Multics and Honeywell 645 version of ring protection was implemented mainly in software, considerable operating system supervisor overhead was entailed particularly when calls to greater or lesser power were made by trapping to a supervisor procedure. What was required was an access control mechanism which had the functional capability to perform effectively its information protection function, was relatively simple in operation, was economic to build, operate and maintain, and did not restrict programming generality. The Honeywell 6000 computer system met these requirements by implementing most of the ring protection mechanism in hardware. Hence special access checking logic, integrated with the segmented addressing hardware was provided to validate each virtual memory reference, and also some special instructions for changing the ring of execution. However certain portions of the ring system particularly outward calls and returns or calls to a lesser power and returns therefrom presented problems which required the ring protection function to be performed by transferring control to a supervisor. What is now needed are further improvements in hardware and techniques that will permit a full implementation of ring protection in hardware/firmware and will meet the criteria of functional capability, economy, simplicity and programming generality.